
package lanqiao;

import java.util.LinkedList;
import java.util.Queue;

// 并查集
//public class Q0595 {
//	static int[] p;
//
//	static int find(int x) {
//		if (p[x] == x) {
//			return x;
//		}
//		int res = find(p[x]);
//		p[x] = res;
//		return res;
//	}
//
//	public static void main(String[] args) {
//		int res = 0;
//
//		int[][] edge = { { 0, 1 }, { 1, 2 }, { 2, 3 }, { 3, 4 }, { 4, 5 }, { 5, 0 }, { 2, 5 } };
//		p = new int[6];
//
//		for (int i = 1; i < 1 << 7; i++) {
//			int num = i;
//			boolean st[] = new boolean[6];
//			for (int j = 0; j < p.length; j++) {
//				p[j] = j;
//			}
//			int start = -1;
//			for (int j = 0; j < 7; j++) {
//				if ((num & 1) == 1) {
//					int a = edge[j][0];
//					int b = edge[j][1];
//					st[a] = true;
//					st[b] = true;
//					p[find(a)] = p[find(b)];
//					start = a;
//				}
//				num >>= 1;
//			}
//			int father = find(start);
//			boolean flag = true;
//			for (int j = 0; j < st.length; j++) {
//				if (st[j] && find(j) != father) {
//					flag = false;
//					break;
//				}
//			}
//			if (flag) {
//				res++;
//			}
//		}
//
//		System.out.println(res);
//	}
//}

// 宽搜检查图的连通性
public class Q0595 {

	public static void main(String[] args) {
		int res = 0;

		int[][] edge = { { 0, 1 }, { 1, 2 }, { 2, 3 }, { 3, 4 }, { 4, 5 }, { 5, 0 }, { 2, 5 } };

		for (int i = 1; i < 1 << 7; i++) {
			int p = i;
			boolean vis[] = new boolean[6];
			int cnt = 0;
			int[][] d = new int[6][6];
			int start = -1;
			for (int j = 0; j < 7; j++) {
				if ((p & 1) == 1) {
					int a = edge[j][0];
					int b = edge[j][1];
					d[a][b] += 1;
					start = a;
					d[b][a] += 1;
					if (!vis[a]) {
						cnt++;
						vis[a] = true;
					}
					if (!vis[b]) {
						cnt++;
						vis[b] = true;
					}
				}
				p >>= 1;
			}

			boolean st[] = new boolean[6];
			Queue<Integer> q = new LinkedList<>();
			q.add(start);
			st[start] = true;
			int num = 1;
			while (!q.isEmpty()) {
				int point = q.poll();
				for (int j = 0; j < st.length; j++) {
					if (d[point][j] >= 1 && !st[j]) {
						num++;
						q.add(j);
						st[j] = true;
					}
				}
			}
			if (num == cnt) {
				res++;
			} else {
				System.out.println(Integer.toBinaryString(i) + " " + cnt + " " + num);
			}
		}

		System.out.println(res);
	}
}

//public class Q0595 {
//
//	public static void main(String[] args) {
//		int res = 0;
//
//		for (int i = 1; i < 1 << 7; i++) {
//			int p = i;
//			boolean[] st = new boolean[7];
//			int cnt = 0;
//			for (int j = 0; j < 7; j++) {
//				if ((p & 1) == 1) {
//					st[j] = true;
//					cnt++;
//				}
//				p >>= 1;
//			}
//			if (cnt == 1) {
//				res++;
//				continue;
//			} else {
//				if (st[0] && !st[1] && !st[5]) {
//					continue;
//				}
//				if (st[1] && !st[0] && !st[6] && !st[2]) {
//					continue;
//				}
//				if (st[2] && !st[3] && !st[6] && !st[1]) {
//					continue;
//				}
//				if (st[3] && !st[2] && !st[4]) {
//					continue;
//				}
//				if (st[4] && !st[3] && !st[6] && !st[5]) {
//					continue;
//				}
//				if (st[5] && !st[4] && !st[6] && !st[1]) {
//					continue;
//				}
//				if (st[6] && !st[1] && !st[2] && !st[4] && !st[5]) {
//					continue;
//				}
//				res++;
//			}
//		}
//
//		System.out.println(res);
//	}
//}
